package org.example.struct.array;

/**
 * @author liyishan
 * @date 2024/2/2 09:50
 * @apiNote
 */

public class Test01071GcdOfStrings {
    public static void main(String[] args) {
        String str1 ="ABABAB";
        String str2 ="ABAB";
        System.out.println(gcdOfStrings1(str1, str2));
    }

    public static String gcdOfStrings(String str1, String str2) {
        int len1 = str1.length(), len2 = str2.length();
        for (int i = Math.min(len1, len2); i >= 1; i--) {
            if (len1 % i == 0 && len2 % i == 0) {
                String t = str1.substring(0, i);
                if (check(t, str1) && check(t, str2)) {
                    return t;
                }
            }
        }
        return "";
    }

    public static String gcdOfStrings1(String str1, String str2) {
        int len1 = str1.length(), len2 = str2.length();
        String str = str1.substring(0,gcd(len1, len2));
        if (check(str,str1) && check(str,str2)) {
            return str;
        }
        return "";
    }

    public static String gcdOfStrings2(String str1, String str2) {
        if(!str1.concat(str2).equals(str2.concat(str1))){
            return "";
        }
        return str1.substring(0,gcd(str1.length(), str2.length()));
    }

    public static int gcd(int a, int b){
        int remainder =  a % b;
        while(remainder != 0){
            a = b;
            b = remainder;
            remainder = a % b;
        }
        return b;
    }
    public static boolean check(String t,String s){
        int lenx = s.length()/t.length();
        StringBuffer ans = new StringBuffer();
        for (int i = 0; i < lenx; i++) {
            ans.append(t);
        }
        return ans.toString().equals(s);
    }
}
